package com.example.question.dp.dp1;

/**
 * @Date 2023-07-19
 * @Author Jonathan
 * 动态规划：消除重复计算问题
 * 1.前缀和
 * 2.动态规划
 * 3.暴力规划
 */
public class Code04_53 {

    public int maxSubArray(int[] nums) {
        // 以i结尾的最大子数组和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

    /**
     * 优化版本  求当前值的时候 实际上只需要知道前一个值就是了
     */
    public int maxSubArray1(int[] nums) {
        // 以i结尾的最大子数组和
//        int[] dp = new int[nums.length];
//        dp[0] = nums[0];
        int maxSum = nums[0];
        int pre = nums[0];
        int cur;
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(pre + nums[i], nums[i]);
            maxSum = Math.max(maxSum, cur);
            pre = cur;
        }
        return maxSum;
    }
}
